package chapter3.part2;

import java.util.*;

/**
 * Created by weimengshu on 2018/9/22.
 */
public class BinaryTreeTraversalStack {

    /**
     * 构建二叉树
     * @param inputList   输入序列
     */
    public static TreeNode createBinaryTree(LinkedList<Integer> inputList){
        TreeNode node = null;
        if(inputList==null || inputList.isEmpty()){
            return null;
        }
        Integer data = inputList.removeFirst();
        //这里的判空很关键。如果元素是空，说明该节点不存在，跳出这一层递归；如果元素非空，继续递归构建该节点的左右孩子。
        if(data != null){
            node = new TreeNode(data);
            node.leftChild = createBinaryTree(inputList);
            node.rightChild = createBinaryTree(inputList);
        }
        return node;
    }

    /**
     * 二叉树非递归前序遍历
     * @param root   二叉树根节点
     */
    public static void preOrderTraveralWithStack(TreeNode root){
        Stack<TreeNode> stack = new Stack<TreeNode>();
        TreeNode treeNode = root;
        while(treeNode!=null || !stack.isEmpty()){
            //迭代访问节点的左孩子，并入栈
            while (treeNode != null){
                System.out.println(treeNode.data);
                stack.push(treeNode);
                treeNode = treeNode.leftChild;
            }
            //如果节点没有左孩子，则弹出栈顶节点，访问节点右孩子
            if(!stack.isEmpty()){
                treeNode = stack.pop();
                treeNode = treeNode.rightChild;
            }
        }
    }

    /**
     * 二叉树非递归中序遍历
     * @param root   二叉树根节点
     */
    public static void inOrderTraveralWithStack(TreeNode root){
        Stack<TreeNode> stack = new Stack<TreeNode>();
        TreeNode treeNode = root;
        while(treeNode!=null || !stack.isEmpty()){
            //迭代访问节点的左孩子，并入栈
            while (treeNode != null){
                stack.push(treeNode);
                treeNode = treeNode.leftChild;
            }

            //如果节点没有左孩子，则弹出栈顶节点，访问节点右孩子
            if(!stack.isEmpty()){
                treeNode = stack.pop();
                System.out.println(treeNode.data); //中序输出
                treeNode = treeNode.rightChild;
            }
        }
    }

    /**
     * 二叉树非递归后序遍历
     * @param root   二叉树根节点
     */
    public static void postOrderTraveralWithStack(TreeNode root){
        Stack<SNode> stack = new Stack<SNode>();
        TreeNode treeNode = root;
        int tag;
        SNode sdata = null;
        while(treeNode!=null || !stack.isEmpty()){
            //迭代访问节点的左孩子，并入栈
            while (treeNode != null){
                sdata = new SNode();
                sdata.p = treeNode;
                sdata.tag = 0;
                stack.push(sdata);
                treeNode = treeNode.leftChild;
            }
            sdata = stack.pop();
            treeNode = sdata.p;
            tag = sdata.tag;
            //如果tag==0，说明该结点还没有遍历它的右孩子
            if(tag == 0){
                sdata.p = treeNode;
                sdata.tag = 1; //开始遍历右孩子
                stack.push(sdata);
                treeNode = treeNode.rightChild;
            }else{
                System.out.println(treeNode.data);
                treeNode = null;
            }
            // 这里是对节点的一次访问(不能确定是第二次还是第三次),需要做判断,如果标志位是1就表示已经完成了两次访问,直接输出并弹出栈帧
            /*while(!stack.isEmpty() && tag == 1){
                SNode temp = stack.pop();
                System.out.println(temp.p.data);
            }*/
        }
    }

    public static List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if(root == null)
            return res;
        LinkedList<TreeNode> stack = new LinkedList<>();
        stack.add(root);
        while(!stack.isEmpty()){
            TreeNode node = stack.pollLast();
            res.add(0, node.data);
            // 先压左后压右,就会先弹出右后弹出左
            if(node.leftChild!= null){
                stack.add(node.leftChild);
            }
            if(node.rightChild != null){
                stack.add(node.rightChild);
            }
        }
        return res;
    }


    /**
     * 二叉树节点
     */
    private static class TreeNode {
        int data;
        TreeNode leftChild;
        TreeNode rightChild;

        TreeNode(int data) {
            this.data = data;
        }
    }

    /**
     * 二叉树标志位
     */
    private static class SNode {
        TreeNode p; //树节点
        int tag; //标志位
    }

    public static void main(String[] args) {
        LinkedList<Integer> inputList = new LinkedList<Integer>(Arrays.asList(new Integer[]{3,2,9,null,null,10,null,null,8,null,4,}));
        TreeNode treeNode = createBinaryTree(inputList);
        System.out.println("前序遍历：");
        preOrderTraveralWithStack(treeNode);
        System.out.println("中序遍历：");
        inOrderTraveralWithStack(treeNode);
        System.out.println("后序遍历：");
        //System.out.println(postorderTraversal(treeNode));
        postOrderTraveralWithStack(treeNode);
    }

}
